package h0902;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 全排列II
 * @date 2024/9/2 21:47
 */
public class PermutationsII {
    public static void main(String[] args) {
        int[] nums={1,2,3};
        System.out.println(permuteUnique(nums));
    }

    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> temp = new LinkedList<>();
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        backTrack(nums, used, res, temp);
        return res;
    }

    private static void backTrack(int[] nums, boolean[] used, List<List<Integer>> res, LinkedList<Integer> temp) {
        if (temp.size() == nums.length) {
            res.add(new LinkedList<>(temp));
            return;
        }
        for (int j = 0; j < nums.length; j++) {
            //TODO 理解了，这个就是每次回溯的时候进行的for循环是从0开始，然后使用used数组标记是否被使用，
            // 如果当前数字等于前一个数字，且还没被使用，意味着就有可能进入下一个排列，而这两个排列是一样的，因此需要跳过。
            if (j > 0 && nums[j] == nums[j - 1] && !used[j-1]) continue;
            if (!used[j]) {
                used[j]=true;
                temp.addLast(nums[j]);
                backTrack(nums, used, res, temp);
                used[j]=false;
                temp.removeLast();
            }
        }
    }
}
